تبادل لینک هوشمند )گراف مسطح گرافی است که می‌تواند در یک صفحه محاط شود. برای مثال یک گراف مسطح را می‌توان به گونه‌ای رسم کرد که یال‌هایش یکدیگر را تنها در راس‌ها قطع کنند.
یک گراف غیر مسطح گرافی است که نمی‌توان آن را به گونه‌ای رسم کرد که یال‌هایش یکدیگر را در نقاطی غیراز راس‌ها قطع نکنند.
گراف مسطحی که بدون تقاطع یالها در صفحه ترسیم شده باشد را صفحه گراف یا گراف محاط در صفحه می‌نامند. یک صفحه گراف را می‌توان به صورت یک گراف مسطح تعریف کرد که هر گره‌ای را به نقطه‌ای در فضای دوبعدی و هر یالی را به خمی در صفحه می‌نگارد به گونه‌ای که نقاط انتهایی هر خم نقاطی هستند که از گره‌ها نگاشته شده‌اند و خم‌ها هیچ اشتراکی با یکدیگر ندارند مگر در نقاط انتهایی.
به سادگی دیده می‌شود که گرافی که قابل ترسیم در صفحه‌است را می‌توان در کره نیز ترسیم کرد و بالعکس.
2)گراف را یک گراف مسطح گوییم هر گاه بتوان آن را روی سطح صاف ( و یا روی سطح کره ) به گونه ای رسم کرد که هیچ دو یالی یکدیگر را قطع نکنند.
همان گونه که در تعریف می بینید، در واقع مسطح بودن گراف معادل است با این که گراف را بتوان روی کره رسم کرد. این که گراف را روی کره ترسیم کنیم، فوایدی حاصل می آورد که در برخی محاسبات آنها خواهیم دید.
و اما اولین سوالی که به ذهن خطور می کند این است که آیا هر گرافی، یک گراف مسطح است یا نه؟! اگر همان طور که در مقدمه آمد سعی کرده باشید گراف را روی صفحه رسم کنید ( از این به بعد منظور از رسم کردن گراف روی صفحه این است که گراف طوری رسم شود که هیچ دو یالی همدیگر را قطع نکنند ). حتی اگر مدت زیادی به آن ور رفته باشید شکست خورده اید. کمی بعد ( همین بخش، به کمک برخی تکنیکها و قضایا اثبات خواهیم کرد که و بسیاری گرافهای دیگر مسطح نیستند. البته برای اینکه کمی قانع شوید نامسطح بودن را همان طوری که در زیر ذکر شده است،می توانید به طور شهودی قبول کنید:
یک گراف روی صفحه رسم می کنیم و نواحی بین یالها را برای روشنتر شدن رنگ می کنیم:
نظرات شما عزیزان:
موضوعات مرتبط: رياضي ، ،
برچسب‌ها:
<-PollName->
خبرنامه وب سایت:
آمار
وب سایت: